package com.cy.letcode.number.最长回文子串;


/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class DynamicSolution {

    public static void main(String[] args) {
        System.out.println(new DynamicSolution().longestPalindrome("ac"));
    }


    /**
     * 动态规划算法
     *
     * @param s 目标串
     * @return 回文子串
     */
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        //初始化一个二维数组
        boolean[][] dps = new boolean[length][length];
        //对二维数据进行填充 默认就是false？
        for (int i = 0; i < length; i++) {
            dps[i][i] = true;
        }
        int maxLength = 1;
        int begin = 0;
        for (int j = 0; j < length; j++) {
            for (int i = j - 1; i >= 0; i--) {
                dps[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dps[i + 1][j - 1]);
//                if (s.charAt(i) == s.charAt(j)) {
//                    if (j - i < 3) {
//                        dps[i][j] = true;
//                    } else {
//                        dps[i][j] = dps[i + 1][j - 1];
//                    }
//                } else {
//                    dps[i][j] = false;
//                }

                if (dps[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLength);

    }


}